A - Nastya Is Reading a Book (签到)
题意
给出每一章的页数范围,然后告诉你当前看到那一页,求还没看完的章节数目
1 |
|
B - Nastya Is Playing Computer Games (模拟)
题意
一排井盖,井盖下面有金币,你需要拿走所有金币,拿走井盖下的金币需要井盖上没有石头
一开始井盖上面都有一个石头。
每一秒你可以进行以下一种操作
1:向左走或者向右走,
2:把一个石头扔到其他任意一个井盖上面
3:取走金币
现在给你起始位置和井盖个数
问你把所有金币取走需要多少步
思路
很明显的一个贪心策略,可以把所有石头都扔到一个不需要的井盖上面 但是第一个扔的还需要再扔回去
然后因为可能要会出生在中间点,所以可以贪心的选择先向左还是向右走
首先 扔石头肯定需要扔n+1次 ,金币也需要捡n次,走路也需要走n-1次 然后就是重复走的距离min(n-k,k-1)
1 |
|
C - Nastya Is Transposing Matrices (神奇)
题意
矩阵a和b 每次可以把a的一个子矩阵按照左对角线翻转,问你能否使a变成b
思路
一开始题目的反转理解错了没想到,
后来发现 如果对于一个2*2的矩阵一次反转就相当于把左下和右上对调。所以只需要保证这一条线的值都相同就肯定可以通过反转变成B
1 |
|
D - Nastya Is Buying Lunch (贪心)
题意
给出一个1-n的数列,然后给你m个关系 如果前面的数正好在后面的数前面一个位置,那么就可以把这两个数交换位置
问你最多可以让最后一个数(a[n])向前走多少步
思路
首先我们可以把点分成两类。
1:可以让n和她交换位置
2:不可以让n和她交换位置
那么题目就是让n最后能有多少个连续的1类点
所以我们考虑贪心能不能把经可能多的一类点向后移动
1 |
|
E - Nastya Hasn’t Written a Legend (线段树)
题意
给你两个序列 $a_1,a_2\dots a_n$ 和 $ k_1,k_2,\dots k_{n-1}$,输入保证$ a_{i}+k_{i}<=a_{i-1}$.
两种操作:
1:区间求$ \sum_{i=l}^{r}a_i$
2:给单点$ a_i$加$x$ 同时会有连锁反应,若$a_p+k_p>a_{p+1}$,则$a_{p+1}$ 更新为$ a_p+k_p$ ,同理更新到$a_p+2$ 知道不能更新
思路
来自群友的做法 (感谢这位巨佬)
首先根据题意会发现一个式子
给$p$位置加上值$x$ 之后,$a_p-\sum_{i=1}^{p-1}k_i$也增加了x。更新之前已知$a_p-\sum_{i=1}^{p-1}k_i\leq a_{p+1}-\sum_{i=1}^{p}k_i$ 如果$a_p+k_p+x >a_{p+1}$
那么$a_{p+1}=a_p+k_p+x$ 并且$a_{p+1}-\sum_{i=1}^{p}k_i=a_p-\sum_{i=1}^{p}k_i+x$ $a_{p+2} $同理
最后:
我们令$b_x=a_x-\sum_{i=1}^{x-1}k_i$,我们给$p$单点加上$x$之后的效果:就是把$i\in[p+1,n]$ 内所有小于$b_p+x$的值赋值为$b_p+x$
所有修改我们已经搞定了,用线段树或者其他数据结构维护就可以了,求和就是$\sum_{i=l}^{r}b_i+\sum_{i=l}^{r}\sum_{j=1}^{i-1}k_j$ 更新就是区间赋值了,因为$b_x$ 满足单调不减性所以直接二分查找右端点
1 |
|